package com.c2b.algorithm.leetcode.base;

/**
 * <a href='https://leetcode.cn/problems/intersection-of-two-linked-lists/'>相交链表(Intersection of Two Linked Lists)</a>
 * <p>给你两个单链表的头节点 headA 和 headB ，请你找出并返回两个单链表相交的起始节点。如果两个链表不存在相交节点，返回 null 。</p>
 * <p>题目数据 保证 整个链式结构中不存在环。</p>
 * <p>注意，函数返回结果后，链表必须 保持其原始结构 。</p>
 *
 * <p>
 * <b>示例：</b>
 * <pre>
 *     <a href='https://leetcode.cn/problems/intersection-of-two-linked-lists/description/'>查看示例</a>
 * </pre>
 * </p>
 *
 * <p>
 * <b>提示：</b>
 *     <ul>
 *         <li>listA 中节点数目为 m</li>
 *         <li>listB 中节点数目为 n</li>
 *         <li>1 <= m, n <= 3 * 10^4</li>
 *         <li>1 <= Node.val <= 10^5</li>
 *         <li>0 <= skipA <= m</li>
 *         <li>0 <= skipB <= n</li>
 *         <li>如果 listA 和 listB 没有交点，intersectVal 为 0</li>
 *         <li>如果 listA 和 listB 有交点，intersectVal == listA[skipA] == listB[skipB]</li>
 *     </ul>
 * </p>
 * <b>进阶：你能否设计一个时间复杂度 O(m + n) 、仅用 O(1) 内存的解决方案？</b>
 *
 * @author c2b
 * @see LC0002AddTwoNumbers_M 两数相加(Add Two Numbers)
 * @see LC0019RemoveNthNodeFromEndOfList_M 删除链表的倒数第 N 个结点(Remove Nth Node From End of List)
 * @see LC0021MergeTwoSortedLists_S 合并两个有序链表(Merge Two Sorted Lists)
 * @see LC0023MergeKSortedLists 合并 K 个升序链表(Merge k Sorted Lists)
 * @see LC0024SwapNodesInPairs_M 两两交换链表中的节点(Swap Nodes in Pairs)
 * @see LC0025ReverseNodesInKGroup_H K 个一组翻转链表(Reverse Nodes in k-Group)
 * @see LC0138CopyListWithRandomPointer_M 随机链表的复制(Copy List with Random Pointer)
 * @see LC0141LinkedListCycle_S 环形链表(Linked List Cycle)
 * @see LC0142LinkedListCycle_II_M 环形链表 II(Linked List Cycle II)
 * @see LC0146LRUCache_M LRU 缓存(LRU Cache)
 * @see LC0148SortList_M 排序链表(Sort List)
 * @see LC0160IntersectionOfTwoLinkedLists_S 相交链表(Intersection of Two Linked Lists)
 * @see LC0206ReverseLinkedList_S 反转链表(Reverse Linked List)
 * @see LC0234PalindromeLinkedList_S 回文链表(Palindrome Linked List)
 * @since 2023/10/31 14:26
 */
public class LC0160IntersectionOfTwoLinkedLists_S {

    public static class Solution {
        public ListNode getIntersectionNode(ListNode headA, ListNode headB) {
            // 分别统计A链表的长度 与 B链表的长度==> 计算A、B链表长度的差值
            int diffLen = 0;
            ListNode tempNode = headA;
            while (tempNode != null) {
                tempNode = tempNode.next;
                ++diffLen;
            }
            tempNode = headB;
            while (tempNode != null) {
                tempNode = tempNode.next;
                --diffLen;
            }
            // 如果 diffLen > 0，说明A链表长;如果 diffLen < 0，说明B链表长
            ListNode longerList = diffLen >= 0 ? headA : headB;
            ListNode shorterList = longerList == headA ? headB : headA;
            // 较长链表先走差值步
            for (int i = 0; i < Math.abs(diffLen) && longerList != null; i++) {
                longerList = longerList.next;
            }
            // 两条链表一起动。此时两条链表一样长，shorterList 不会出现空指针
            while (longerList != null && shorterList != null && longerList != shorterList) {
                longerList = longerList.next;
                shorterList = shorterList.next;
            }
            return longerList;
        }
    }

    public static void main(String[] args) {
        Solution solution = new Solution();
        ListNode node4_1 = new ListNode(4);
        ListNode node1_1 = new ListNode(1);
        ListNode node5_1 = new ListNode(5);
        ListNode node6 = new ListNode(6);
        ListNode node1_2 = new ListNode(1);
        ListNode node8 = new ListNode(8);
        ListNode node4_2 = new ListNode(4);
        ListNode node5_2 = new ListNode(5);
        node4_1.next = node1_1;
        node1_1.next = node8;
        node8.next = node4_2;
        node4_2.next = node5_2;
        node5_1.next = node6;
        node6.next = node1_2;
        node1_2.next = node8;
        Printer.printListNode(solution.getIntersectionNode(node4_1, node5_1));
    }
}
